1. Technical Field
The present invention relates in general to an improved method and system for managing communications networks. In particular, the present invention relates to a method and system for scheduling the arrival rate of data packets among a plurality of data queues. More particularly, the present invention relates to a method and system for allocating bandwidth between memory queues and corresponding output queues having differing service rates. Still more particularly, the present invention provides a selection mechanism by which output queue threshold criteria are compared with current output queue occupancy data to service one among a plurality of data queues during each of a repeating time interval, such that queue underflow and overflow are minimized.
2. Description of the Related Art
In switch design it is necessary to schedule traffic to multiple data ports which may have different output flow rates. In this context, a xe2x80x9cdata portxe2x80x9d may be referred to interchangeably as a xe2x80x9cdata queuexe2x80x9d. Similarly, and consistent with conventional queueing theory terminology, the xe2x80x9coutput flow ratexe2x80x9d of a queue may be referred to as the xe2x80x9cservice ratexe2x80x9d of the queue in question. All data in memory exists in fixed cell sizes. Each cell resides within a particular memory queue, and is labeled with a designator that identifies a given output port as its destination. At each time step, a scheduler may either declare a pause (do nothing to any cells) or choose exactly one memory queue, extract the first cell from that queue, and move that cell into the output queue of the same label, as illustrated in FIG. 1.
Furthermore, at each time step some irregular but constant fraction of a cell is taken from each output queue. The irregular function reflects the asynchronous nature of the scheduler and the external media into which output ports feed. To avoid underflow, a fundamental and obviously necessary assumption is that the sum of the output fractions must be less than or equal to one.
To further clarify the scheduler problem, it should be noted that the configuration depicted in FIG. 1 is susceptible to two constraints which must be addressed. The first is underflow which, as the term is utilized herein, refers to a queue that, once started, becomes empty even when data designated for that port is currently available within memory buffers 106. Underflow occurs in the scheme depicted in FIG. 1 when scheduler 102 has begun scheduling a memory queue but then fails to allocate input data from memory buffers 106 to one of output queues 104 at a rate sufficient to compensate for the output flow rate, or queue bandwidth of one of the queues. The problems caused by underflow include degradation in Quality of Service (QoS) guarantees and increased network congestion.
Whereas underflow results in data queues being permitted by scheduler 102 to become empty, overflow results when, in trying to build up an excessive surplus in an output queue, scheduler 102 allocates input data to one of queues 104 at a rate faster than the queue""s respective service bandwidth (output flow rate), the queue""s occupancy will rise until an unacceptable overflow condition occurs. Like underflow, overflow results in degraded network efficiency and predictability and in increased congestion.
From the foregoing, it can be appreciated that a need exists for a method and system for scheduling the data arrival rate from a single source link to multiple data queues such that the minimum level of occupancy within each of the queues in maximized. Implementation of such a method and system would prevent overflow and underflow from occurring, thereby enhancing the efficiency and reliability of telecommunications networks.
It is therefore an object of the invention to provide an improved method and system for managing communications networks.
It is another object of the invention to provide a method and system for scheduling the arrival rate of data packets among a plurality of data queues.
It is a further object of the present invention to provide a method and system for allocating bandwidth of a single source link among a plurality of output queues having differing service rates.
It is still another object of the present invention to provide a selection mechanism by which queue threshold criteria are compared with current queue occupancy data to increment one among a plurality of data queues during each of a repeating time interval, such that queue underflow and overflow are minimized.
The above and other objects are achieved as is now described. A method and system are disclosed for allocating data input bandwidth from a source link to a plurality of N data queues each having a variable occupancy value, Qi(t), and a constant decrement rate, Di, where i designated the ith queue among the N queues. First, a threshold occupancy value, T, is designated for the N queues. During each time step of a repeating time interval, xcex94t, the occupancy value, Qi, is compared with T. In response to each and every of said N data queues having occupancy values exceeding T, pausing data transmission from the source link to the N data queues, such that overflow within the data queues is prevented. In response to at least one of the N data queues having an occupancy value less than or equal to T, selecting one among the N data queues to be incremented, and incrementing the selected data queue, such that underflow of the selected queue is prevented. In the context of scheduling one cell per time step, the value of T is one. Furthermore, the method of the present invention guarantees that output port occupancy shall never, in that context, exceed two cells.